import java.util.Iterator;
/**
 * Scaling FF algorithm
 * @author 捣蛋鬼x
 *
 */
public class ScalingFF {
	public ScalingFF() {

	}
/**
 * Find max flow of the flow networks with Max Scaling Ford Fulkerson algorithm
 * @param G Input Simple Graph
 * @param s source point
 * @param t sink point
 * @return max flow of the 
 * @throws Exception when out of java heap
 */
	public static int maxFlow(SimpleGraph G, Vertex s, Vertex t)
			throws Exception {
		SimpleGraph residual;
		int flow = 0, current, scale, maxcap = 0;
		Iterator i;
		Edge e;
		Vertex v, previous;
		VertexData vdata = new VertexData();
		EdgeData edata;

		// find the maximum capacity
		for (i = G.edges(); i.hasNext();) {
			e = (Edge) i.next();
			try {
				edata = new EdgeData(((Double) e.getData()).intValue(), 0);
			} catch (Exception e2) {
				// TODO: handle exception
				System.out.println("stop");
				return 0;
			}
			e.setData(edata);
			maxcap = Math.max(maxcap, edata.getCapacity());
			// if (maxcap<edata.getCapacity())
			// maxcap=edata.getCapacity();
		}
		// System.out.println(maxcap);

		//Find the scale
		scale = maxpower2(maxcap);
		// System.out.println(scale);
		while (scale >= 1) {

			// set all visited to false
			for (i = G.vertices(); i.hasNext();) {
				v = (Vertex) i.next();
				// vdata = (VertexData) v.getData();
				vdata.setVisited(false);
				v.setData(vdata);
			}

			// Iterator tempt = G.edges();
			// while(tempt.hasNext())
			// {
			// Edge et = (Edge) tempt.next();
			// System.out.print(et.getFirstEndpoint().getName()+ "-" +
			// et.getSecondEndpoint().getName()+
			// " "+((EdgeData)et.getData()).getCapacity()+"\n");
			// }

			residual = FindPath.DFS(G, s, t, new SimpleGraph(), scale - 1);
			// System.out.println(path.numEdges());
			while (residual.numEdges() > 0) {

				current = maxcap;
				previous = s;
				// find the bottleneck
				for (i = residual.edges(); i.hasNext();) {
					e = (Edge) i.next();
					edata = (EdgeData) e.getData();
					if (e.getFirstEndpoint() == previous) {
						current = Math.min(current, edata.getAvailable());
						previous = e.getSecondEndpoint();
					} else {
						current = Math.min(current, edata.getFlow());
						previous = e.getFirstEndpoint();
					}

				}

				previous = s;
				for (i = residual.edges(); i.hasNext();) {
					e = (Edge) i.next();
					edata = (EdgeData) e.getData();
					if (e.getFirstEndpoint() == previous) {
						edata.setFlow(edata.getFlow() + current);
						previous = e.getSecondEndpoint();
					} else {
						edata.setFlow(edata.getFlow() - current);
						previous = e.getFirstEndpoint();
					}

				}
				flow += current;
				// System.out.println(flow);

				// set all vertexData visited to false
				for (i = G.vertices(); i.hasNext();) {
					v = (Vertex) i.next();
					vdata.setVisited(false);

					v.setData(vdata);
				}
				residual = FindPath.DFS(G, s, t, new SimpleGraph(), scale - 1);
			}
			scale = scale / 2;
		}
		return flow;
	}

	private static int maxpower2(int x) {
		int y = 1;
		while (y * 2 <= x)
			y = y * 2;
		return y;
	}

	public static void main(String[] args) throws Exception {
		SimpleGraph G = new SimpleGraph();
		Vertex s = null, t = null;
		Edge e;
		int flow;
		Iterator i;
		EdgeData edata;
//		GraphInput.LoadSimpleGraph(G,
//				"F:/workspace/FlowNetwork/random.txt");
//		System.out.print("Please enter the full path and file name for the input data: ");
//        String userinput;
//        userinput = KeyboardReader.readString();
//		GraphInput.LoadSimpleGraph(G,userinput);

//		GraphInput.LoadSimpleGraph(G, "Random/random.txt");
		
		for (i = G.vertices(); i.hasNext();) {
			Vertex v = (Vertex) i.next();
			if (v.getName().equals("s"))
				s = v;
			else if (v.getName().equals("t"))
				t = v;
		}
		//get running time
		long startTime = System.currentTimeMillis();
		flow = maxFlow(G, s, t);
		long endTime = System.currentTimeMillis();
		
//		System.out.println("After iterate the flow in each edge");
//		for (i = G.edges(); i.hasNext();) {
//			e = (Edge) i.next();
//			edata = (EdgeData) e.getData();
//			System.out.println("Edge: " + " " + e.getFirstEndpoint().getName()
//					+ "-" + e.getSecondEndpoint().getName() + " "
//					+ edata.getFlow() + "/" + edata.getCapacity());
//		}
		System.out.println("running time�� " + (endTime - startTime) + "ms");
		System.out.println("max flow: " + flow);
		
		
	}
}
